package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题

	　　Given an array of integers, every element appears twice except for one. Find that single one.
	
	Note:
	Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
	

题目大意
	翻译：给定一个整形数组，其中除了一个元素出现一次外，其他元素均出现两次。找到那个出现一次的元素
	
	注意：算法应具有线性时间复杂度。你能不用额外内存实现它么？

解题思路
	通过异或运算实现。
	
	原理：异或运算中，两个二进制位相同取零，不同则取1.
		异或特性：
		
			（1）顺序无关：即若有多个元素相异或，则异或元素可以随意交换顺序，不会影响结果
			
			（2）对相同的数异或两次等于没有异或：即相当于+x和-x
	即：eg：new int[] {1, 1, 2, 2, 3, 4, 4, 5, 5}
		根据特性（1）：可以将数组遍历一遍，一排异或过去
		根据特性（2）：1^1=0, 2^2=0, 4^4=0, 5^5=0, 剩下一个3, 也就是我们要找的数字
		
 * @Date 2017-09-14 11：23
 */
public class _136_Single_Number {
	
	 public int singleNumber(int[] nums) {
		 int rs = nums[0];
		 for (int i = 1; i < nums.length; i ++) {
			 rs ^= nums[i];
		 }
		 return rs;
	 }
	
	public static void main(String[] args) {
		_136_Single_Number obj = new _136_Single_Number();
		LogUtils.println("结果", 
				obj.singleNumber(
						new int[] {1, 1, 2, 2, 3, 4, 4, 5, 5}		//3只出现一次
				));
		LogUtils.println("结果", 
				Character.isLetter(" ".charAt(0)));
	}

}
